package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC756 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public boolean pyramidTransition(String bottom, List<String> allowed) {
            Map<String, Set<String>> allowMap = new HashMap<>();
            for (String allow : allowed) {
                String key = allow.substring(0, 2), value = allow.substring(2, 3);
                if (!allowMap.containsKey(key)) allowMap.put(key, new HashSet<>());
                allowMap.get(key).add(value);
            }

            return pyramidTransitionDFS(new StringBuilder(bottom), 0, null, allowMap);
        }

        public boolean pyramidTransitionDFS(StringBuilder curBottom, int curLineStartPos, StringBuilder nextLayerBottom, Map<String, Set<String>> allowMap) {
            if (curBottom.length() <= 1) return true;
            if (curLineStartPos >= curBottom.length()) return true;
            if (null == nextLayerBottom) nextLayerBottom = new StringBuilder();


            String nextKey = curBottom.substring(curLineStartPos, curLineStartPos + 2);
            if (!allowMap.containsKey(nextKey)) return false;
            for (String nextValue : allowMap.get(nextKey)) {
                nextLayerBottom.append(nextValue);
                boolean curKeyTryResult = false;
                if (curLineStartPos == curBottom.length() - 2) {
                    curKeyTryResult = pyramidTransitionDFS(nextLayerBottom, 0, null, allowMap);
                } else {
                    curKeyTryResult = pyramidTransitionDFS(curBottom, curLineStartPos + 1, nextLayerBottom, allowMap);
                }

                if (curKeyTryResult) return true;
                nextLayerBottom.delete(nextLayerBottom.length() - 1, nextLayerBottom.length());
            }

            return false;
        }
    }

    public void run() {
        Solution solution = new Solution();
        String bottom = "BCD";
        String[] allowed = {"BCG", "CDE", "GEA", "FFF"};
        System.out.println(solution.pyramidTransition(bottom, Arrays.asList(allowed)));
    }

    public static void main(String[] args) throws Exception {
        LC756 an = new LC756();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
